#include<stdio.h>
/*
	递归：
		递归是一种在函数定义中使用'函数自身'的方法。
		递归函数通常通过调用自身来解决问题，通常会有一个或多个基准条件（或称为终止条件）来防止无限递归，
		确保递归调用最终可以结束。

--------------------------------------------------------------------------------------------------------------------------------------------------

	递归基本思想：将问题分解为更小的子问题，直到问题足够简单，可以直接解决。

--------------------------------------------------------------------------------------------------------------------------------------------------
	递归核心：

	递归调用：函数调用自身。

	基准条件（Base Case）：当满足某个条件时，递归停止。

	递归返回：当递归调用结束后，控制权会返回到上一层调用。

--------------------------------------------------------------------------------------------------------------------------------------------------

	递归解决问题的过程可以分为两个主要步骤：
	1.递归调用：函数在解决问题的过程中调用自身来处理子问题。

	2.基准条件：设定一个条件，当满足该条件时，函数不再进行递归调用，而是直接返回结果。
			   递归在解决某些问题时非常有效，尤其是那些可以被分解为相同问题的子问题的情况。例如，计算阶乘、斐波那契数列、树和图的遍历等。

--------------------------------------------------------------------------------------------------------------------------------------------------

	优势：递归的思考角度跟通常的迭代（你可以理解为 for 循环之类的）迥然不同，所以有时候使用迭代思维解决不了的问题，使用递归思维则一下子迎刃而解。
	<说人话就是在特定范围内，用递归解决问题会快一些>

	劣势：递归的执行效率通常比迭代低很多，所以递归程序要更消耗时间；
		由于递归函数是不断调用函数本身，在最底层的函数开始返回之前，程序都是一致在消耗栈空间的，所以递归程序要“吃”更多的内存空间；
		递归的结束条件设置非常重要，因为一旦设置错误，就容易导致程序万劫不复（崩溃）。

--------------------------------------------------------------------------------------------------------------------------------------------------

	慎用递归：递归不怎么省下内存，有时候递归效率更低，而且使用递归对于一个程序设计来说，递归会导致你的同伴看不懂


*/
//程序1
//for循环实现递归计算阶乘
#include<stdio.h>
long fact1(int num);

long fact1(int num)
{
	long result;
	for (result = 1; num > 1; num--)
	{
		result *= num;
	}
	return result;
}

void test1(void)
{
	int num;

	printf("请输入一个正整数：");
	scanf("%d", &num);
	
	printf("%d的阶乘是：%d", num, fact1(num));

}


//程序2
//有返回值的递归算阶乘
#include<stdio.h>

long fact2(int num);

long fact2(int num)
{
	long result;
	if (num > 1) return result = num * fact2(num - 1);


	else result = 1;// 基线条件;
	return result;
	/*
	fact2(5)<递>
+   |
+   |--- 5 * fact2(4)
+   |       |
+   |       |--- 4 * fact2(3)
+   |       |       |
+   |       |       |--- 3 * fact2(2)
+   |       |       |       |
+   |       |       |       |--- 2 * fact2(1)
+   |       |       |       |       |
+   |       |       |       |       |--- 1 (基准条件)
	当 fact2(5) 被调用时，它会计算 5 * fact2(4)。
	fact2(4) 会计算 4 * fact2(3)。
	fact2(3) 会计算 3 * fact2(2)。
	fact2(2) 会计算 2 * fact2(1)。
	fact2(1) 返回 1，作为基准条件的结果。
	然后，计算的结果会一层层返回并相乘，最终 fact2(5) 返回 120。<归>

	在程序执行过程中，每一次函数调用都会在调用栈中开辟一个新的栈帧（stack frame）。对于递归调用，这意味着每次调用自身都会在栈上增加一个新的栈帧，直到基准条件被满足为止。之后，栈帧会逐渐被释放，结果返回给上一级调用。


	*/

}  

void test2(void)
{
	int num;
	printf("请输入一个数：");
	scanf("%d", &num);
	printf("%d的阶乘是:%d", num, fact2(num));
}



//程序3
//无返回值的递归
#include <stdio.h>

void up_and_down(int n);

void up_and_down(int n)
{
	printf("%d ", n);
	if (n > 0)//递归条件
	{
		up_and_down(--n);//递归调用
		/*
			试着想一想，为什么不能用n--；

			使用 --n 的情况：
				在递归调用 up_and_down 函数之前，n 的值先被减 1。
				这样递归调用的是 n 减 1 后的值。
				递归终止条件是 n <= 0，所以在每次递归调用时，n 都会减少，确保最终会达到终止条件。

			使用 n-- 的情况：
				在递归调用 up_and_down 函数时，传入的是 n 的当前值。
				递归调用之后，n 的值才会被减 1。
				这可能导致无限递归。
				例如，如果初始 n 的值为 3，在第一次调用 up_and_down(3) 时，n 传入的是 3，但是函数执行完返回调用栈时，n 变为 2。
				然后 n 再次传入 3，继续递归调用，导致无法达到终止条件
		
		*/

		//递归实现原理
		/*up_and_down(3)
			|
			v
			up_and_down(2)
			|
			v
			up_and_down(1)
			|
			v
			up_and_down(0)
			|
			v
			(不再递归, 打印0)
			/ \
			v   v
			(打印0) (返回到up_and_down(1))
			|
			v
			(打印1) (返回到up_and_down(2))
			|
			v
			(打印1) (返回到up_and_down(3))
			|
			v
			(打印2) (结束)
		*/
		//up_and_down 函数虽然没有显式返回一个值，但它并不是不具备返回值。在C语言中，void 类型的函数不返回任何值，但这并不意味着它不能执行其他操作。
		// printf 语句是用来输出内容到控制台的，并不会影响函数的返回值类型。因为递归的目的是执行函数体内的操作，而不是获取返回值


	}
	printf("%d ", n);//基线条件： n <= 0时，递归终止
}

void test3(void)
{
	int n;

	printf("请输入一个整数：");
	scanf("%d", &n);

	up_and_down(n);
	putchar('\n');

}


//程序4
//课后作业——编写一个程序，反向打印用户输入的英文句子,递归方法1
#include<stdio.h>
#include<string.h>

void recursion(char*, int,int );
int CalculateStringSize(char* s);

//计算字符串大小
int CalculateStringSize(char* s)
{
	int len = strlen(s);
	return len;
}

//反向打印
void recursion(char* s, int len, int n)
{
	if (len >= 0)
	{
		printf("%c", s[len]);//从数组最后一位开始向前打印
		recursion(s, --len,n);
	}
}


void test4(void)
{
	char s[100];
	printf("请输入一个字符串：");
	fgets(s, 100, stdin);
	for (int i = 0; i < 100; i++)
	{
		if (s[i] == '\n')
		{
			s[i] = '\0';
			break;
		}
	}
	int len = CalculateStringSize(s);
	int n = len;
	recursion(s, len,n);

}

//程序5
//课后作业——编写一个程序，反向打印用户输入的英文句子（小甲鱼代码版本）
#include<stdio.h>

void getInput();

void getInput()
{
	int ch;
	if ((ch = getchar()) != '\n')
	{
		getInput();
	}
	else
	{
		printf("反向输出:");
	}
		
	putchar(ch);


}

void test5(void)
{
	char ch;
	printf("请输入一段字符串：");
	getInput();
	putchar('\n');
}

//程序6
//利用迭代反向打印字符串
#include<stdio.h>
#include<string.h>

char* getinput();
int Calculate_String_Size(char* s);
void printf(char* s, int len);

//输入函数
char* getinput()
{
	char* s = new char[100];
	fgets(s, 100, stdin);
	for (int i = 0; i < 100; i++)
	{
		if (s[i] == '\n')
		{
			s[i] = '\0';
			break;
		}
	}
	return s;
}

//计算大小
int Calculate_String_Size(char* s)
{
	int len = strlen(s);
	return len;
}

//打印结果
void print(char* s, int len)
{
	for (int j = len; j >= 0; j--)
	{
		printf("%c", s[j]);
	}
}

//函数调用
void test6(void)
{
	printf("请输入一个字符串：");
	char* s = getinput();
	int len = Calculate_String_Size(s);
	print(s, len);


}


//程序7
//进制转化

#include<stdio.h>

void Transformation(unsigned long n);
void Transformation(unsigned long n)
{
	int r;
	r = n % 2;
	if (n >= 2)
	{
		Transformation(n / 2);
	}
	putchar('0' + r);

}

void test7(void)
{
	unsigned long number;
	printf("请输入一个十进制数据：");
	scanf("%lu", &number);

	Transformation(number);
	printf("\n");

}


//主函数
int main() 
{
	test3();
	return 0;
}
/*
* 
	从这节课开始，你就会发现，我书写的函数开始变多了，主函数基本没啥条件了，之前我们的代码都是放在主函数里面的，
	分开设计函数的功能，有这些优点：
	将代码分开创建函数来实现不同的功能有多个优点，这不仅有助于提高代码的可读性，还能提升代码的可维护性和可重用性。以下是具体原因：

		1.可读性：函数划分可以将代码组织得更加清晰、有条理。每个函数可以专注于实现一个具体的逻辑或功能。这样，代码的逻辑结构更加直观，更容易理解和阅读。

		2.可维护性：将功能模块化后，修改或调试代码时，只需关注相关函数即可，无需遍历整个程序。这降低了出错的风险，也减少了对其他部分的影响。

		3.可重用性：通过将代码封装在函数中，可以方便地在不同的程序或同一程序的不同部分中重用这些函数。而如果所有逻辑都写在主函数内，那么重用这部分逻辑就需要复制粘贴，这不仅增加了代码量，还可能导致错误。

		4.简化调试：模块化的代码可以使得调试过程更加容易。当程序出现问题时，可以通过逐步调试各个函数来定位问题，而不是在一个庞大的主函数中进行复杂的调试。

		5.代码的组织结构：函数划分有助于更好地组织代码结构，使得代码更加模块化。模块化设计可以帮助开发者更好地管理代码，尤其是在大型项目中。

		6.分而治之：通过分解问题并使用递归函数来解决，可以更容易地实现复杂问题的求解。递归函数通常会在解决复杂问题时被调用自身来处理子问题，直到问题足够简单以直接解决。

		7.避免重复代码：如果某个功能需要在多个地方使用，将其封装为一个函数可以避免重复编写相同的代码，从而减少工作量和出错的概率。

	也就是有效避免重复使用同一个命名变量，局部变量出了函数立即销毁，可以避免同名变量出现

*/
